package tencent_practice;

/**
 * 自己的动态规划失败
 * 参考评论区大神题解
 */
public class Tencent_53_maxSubArray {
    /**
     * 动态规划，可行
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }
        int res = nums[0];
        for (int i = 0; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    // TODO 抽空写一下分治法
    // 开始使用分治法
    class Solution {
        public int maxSubArray(int[] nums) {
            int len = nums.length;
            if (len == 0) {
                return  0;
            }
            return maxSubArray(nums, 0, len - 1);
        }

        public int maxCrossingSum(int[] nums, int left, int mid, int right) {
            int leftSumMax = Integer.MIN_VALUE;
            int sum = 0;
            for (int i = mid; i >= left; i--) {
                sum += nums[i];
                if (sum > leftSumMax) {
                    leftSumMax = sum;
                }
            }
            sum = 0;
            int rightSumMax = Integer.MIN_VALUE;
            for (int i = mid + 1; i <= right; i++) {
                sum += nums[i];
                if (sum > rightSumMax) {
                    rightSumMax = sum;
                }
            }
            return leftSumMax + rightSumMax;
        }

        public int maxSubArray(int[] nums, int left, int right) {
            if (left == right) {
                return nums[left];
            }
            int mid = left + (right - left) / 2;
            return getMax(maxSubArray(nums, left, mid),
                    maxSubArray(nums, mid + 1, right),
                    maxCrossingSum(nums, left, mid, right));
        }

        private int getMax(int num1, int num2, int num3) {
            return Math.max(num1, Math.max(num2, num3));
        }
    }
}
